//
// Created by francklinson on 2021/5/25.
//
/*给你一棵二叉树，请你返回满足以下条件的所有节点的值之和：

该节点的祖父节点的值为偶数。（一个节点的祖父节点是指该节点的父节点的父节点。）
如果不存在祖父节点值为偶数的节点，那么返回0 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sum-of-nodes-with-even-valued-grandparent
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。*/
#include <vector>
#include <iostream>
#include <queue>

using namespace std;

//Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
private:
    int ansSum = 0;
public:
    int sumEvenGrandparent(TreeNode *root) {
//        helper(nullptr, nullptr, root);
        helper2(1, 1, root);
        return ansSum;
    }

    void helper(TreeNode *grandpa, TreeNode *father, TreeNode *root) {
        // 储存祖父节点 父节点 信息
        // 空节点 返回
        if (root == nullptr) return;
        // 祖父节点是偶数  加值
        if (grandpa != nullptr and grandpa->val % 2 == 0) ansSum += root->val;
        helper(father, root, root->left);
        helper(father, root, root->right);
    }

    void helper2(int grandpaVal, int fatherVal, TreeNode *root) {
        // 只储存数值信息也可以
        if (root == nullptr) return;
        if (grandpaVal % 2 == 0) ansSum += root->val;
        helper2(fatherVal, root->val, root->left);
        helper2(fatherVal, root->val, root->right);

    }
};

class Solution2 {
public:
    int sumEvenGrandparent(TreeNode *root) {
        // bfs 将偶数节点的孙子节点加入答案
        queue<TreeNode *> q;
        q.push(root);
        int ans = 0;
        while (!q.empty()) {
            TreeNode *node = q.front();
            q.pop();
            if (node->val % 2 == 0) {
                if (node->left) {
                    if (node->left->left) {
                        ans += node->left->left->val;
                    }
                    if (node->left->right) {
                        ans += node->left->right->val;
                    }
                }
                if (node->right) {
                    if (node->right->left) {
                        ans += node->right->left->val;
                    }
                    if (node->right->right) {
                        ans += node->right->right->val;
                    }
                }
            }
            if (node->left) {
                q.push(node->left);
            }
            if (node->right) {
                q.push(node->right);
            }
        }
        return ans;
    }
};

int main() {
    auto n1 = TreeNode(6), n2 = TreeNode(7), n3 = TreeNode(8), n4 = TreeNode(2), \
 n5 = TreeNode(7), n6 = TreeNode(1), n7 = TreeNode(3), n8 = TreeNode(9), \
 n9 = TreeNode(1), n10 = TreeNode(4), n11 = TreeNode(5);
    n1.left = &n2;
    n1.right = &n3;
    n2.left = &n4;
    n2.right = &n5;
    n4.left = &n8;
    n5.left = &n9;
    n5.right = &n10;
    n3.left = &n6;
    n3.right = &n7;
    n7.right = &n11;
    Solution sol;
    cout << sol.sumEvenGrandparent(&n1) << endl;
    return 0;

}